// https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/

// 算法思路：
// dp[i] 表示以 arr[i] 结尾的最长等差子序列长度
// 使用哈希表 hs 记录每个数值最近出现的位置
// 对于每个元素 arr[i]，查找是否存在前驱元素 goal = arr[i] - difference
// 如果存在，则 dp[i] = dp[前驱位置] + 1，否则保持初始值 1
// 更新哈希表并记录最大值


#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>    

class Solution 
{
public:
    int longestSubsequence(vector<int>& arr, int difference) 
    {
        int m = arr.size();
        if (m == 1) return 1;

        vector<int> dp(m, 1);
        unordered_map<int, int> hs;
        hs[arr[0]] = 0;

        int ret = 1;
        for (int i = 1 ; i < m ; i++)
        {
            int goal = arr[i] - difference;
            if (hs.count(goal))
            {
                dp[i] = dp[hs[goal]] + 1;
            }

            hs[arr[i]] = i;
            ret = max(ret, dp[i]);
        }

        return ret;
    }
};

int main()
{
    int d1 = 1, d2 = 1;
    vector<int> v1 = {1,2,3,4}, v2 = {1,3,5,7};
    Solution sol;

    cout << sol.longestSubsequence(v1, d1) << endl;
    cout << sol.longestSubsequence(v2, d2) << endl;

    return 0;
}